package offer;

public class Solution49 {
    public int nthUglyNumber(int n) {
        long[] dp = new long[n];
        dp[0] = 1;
        int p2, p3, p5;
        p2 = p3 = p5 = 0;
        for (int i = 1; i < n; i++) {
            long a = dp[p2] * 2, b = dp[p3] * 3, c = dp[p5] * 5;
            dp[i] = Math.min(a, Math.min(b, c));
            if (dp[i] == a) {
                p2++;
            }
            if (dp[i] == b) {
                p3++;
            }
            if (dp[i] == c) {
                p5++;
            }
        }
        return (int) dp[n - 1];
    }
}
